{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "# 第3章 k近邻法\n",
    "\n",
    "## 习题3.1\n",
    "&emsp;&emsp;参照图3.1，在二维空间中给出实例点，画出$k$为1和2时的$k$近邻法构成的空间划分，并对其进行比较，体会$k$值选择与模型复杂度及预测准确率的关系。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "**解答：**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**解答思路：**\n",
    "1. 参照图3.1，使用已给的实例点，采用sklearn的KNeighborsClassifier分类器，对k=1和2时的模型进行训练\n",
    "2. 使用matplotlib的contourf和scatter，画出k为1和2时的k近邻法构成的空间划分\n",
    "3. 根据模型得到的预测结果，计算预测准确率，并设置图形标题\n",
    "4. 根据程序生成的图，比较k为1和2时，k值选择与模型复杂度、预测准确率的关系"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**解答步骤：**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**第1、2、3步：使用已给的实例点，对$k$为1和2时的k近邻模型进行训练，并绘制空间划分**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from matplotlib.colors import ListedColormap\n",
    "import matplotlib.pyplot as plt\n",
    "from sklearn.neighbors import KNeighborsClassifier\n",
    "import numpy as np\n",
    "%matplotlib inline\n",
    "\n",
    "data = np.array([[5, 12, 1],\n",
    "                 [6, 21, 0],\n",
    "                 [14, 5, 0],\n",
    "                 [16, 10, 0],\n",
    "                 [13, 19, 0],\n",
    "                 [13, 32, 1],\n",
    "                 [17, 27, 1],\n",
    "                 [18, 24, 1],\n",
    "                 [20, 20, 0],\n",
    "                 [23, 14, 1],\n",
    "                 [23, 25, 1],\n",
    "                 [23, 31, 1],\n",
    "                 [26, 8, 0],\n",
    "                 [30, 17, 1],\n",
    "                 [30, 26, 1],\n",
    "                 [34, 8, 0],\n",
    "                 [34, 19, 1],\n",
    "                 [37, 28, 1]])\n",
    "# 得到特征向量\n",
    "X_train = data[:, 0:2]\n",
    "# 得到类别向量\n",
    "y_train = data[:, 2]\n",
    "\n",
    "#（1）使用已给的实例点，采用sklearn的KNeighborsClassifier分类器，\n",
    "# 对k=1和2时的模型进行训练\n",
    "# 分别构造k=1和k=2的k近邻模型\n",
    "models = (KNeighborsClassifier(n_neighbors=1, n_jobs=-1),\n",
    "          KNeighborsClassifier(n_neighbors=2, n_jobs=-1))\n",
    "# 模型训练\n",
    "models = (clf.fit(X_train, y_train) for clf in models)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAA2cAAAE/CAYAAADCCbvWAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuMCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy86wFpkAAAACXBIWXMAAAsTAAALEwEAmpwYAABkkklEQVR4nO3de3xb533n+c9DgiR4B3WlJEqGZMm6+BLYlm3ZkW0kTlv3mrRxMk3aTtCbO7vtbNl2dsftXsrMzM6os22K7rbbaXpZpG3cNuM0vTdtmuTYkW06lm3Ylm3KkiWYoiRIoiSQgiiIBPHsH+eAAi+SSIrkAcDv+/XCS8A5IM7vEBQe/M7zPL/HWGsRERERERERf9X4HYCIiIiIiIgoORMRERERESkLSs5ERERERETKgJIzERERERGRMqDkTEREREREpAwoORMRERERESkDSs4qlDEma4zZMsvnWmPM1mvsixlj9i9sdAvHGPMjxph/vs7+qDFmYA6v5xhjfmphopv1MRuMMW8bYzqX8rgyM2PM54wx/8bvOERkeVB7PbFf7bVMYoy5yxjzgt9xlBslZwvEGJMyxnyk5PEPG2MuGGMeneG5Ue8D+HembN9vjInN5njW2hZr7dGbDrzMWWu/aK39zuLj6zVcS8UY80ljzAvGmBFjjDOLH3kSeM5am57yOj3e+dy/KIGWGWPMzxljDhhjrhhjEjPsf8wY0+f9Xr9pjLmlZJ8xxvyaMeacd/uvxhjj7QsYY/7cGJMxxvyjMaa15Of+V2PML0w51P8F/K/GmPpFOlURKWNqrxdHmbbXv26MOWyMuei1L//6Bj+i9howxoSNMf/g/b9IG2N+2xgTKNn/SWPMO97v9W1jzMdK9n3aGHPKGHPMGBMt2X6r992ptrjNWvsGkDHGfP/SnFllUHK2CIwxnwF+B/hea+2z13jaJeBfG2PCSxbYIiv9j1vlzgNxYN8sn/8zwJ+UbvASix/zXuszCxncjfj4Pp0E/hPwR1N3GGNWAX8J/O/ACuAA8BclT3kS+BjwAeAu4Ptwf68APwRYYBUwXNxujNkMfD/w/5Qey1p7CugDfmBBzkpEKpba66p3CbcdaMdta3/LGPPQdZ6v9tr1/wJngHVABHgU+B+9mDYAfwr8ItAG/M/A08aYNV68+4B7gH8L/HbJa/7fwC9aa8enHOuLXG3PBSVnC84Y8yTwG8B3WWuv11WbARLAr17ntX7CuzJxwRjzT1N6EiauSBljVhpj/tYYM2yMedkY85/M9KEPH/GuHl0wxvxOsdfh6suZ/8cYM+RdWXqsZMd6Y8zfGGPOG2OOGGN+umRfjzHmGWPMnxpjhoGYMeZ+r3dk2Bhz2hjzuWuc27PGmI979/d65/M93uOPGGOS3v2JYRzGmOe8H3/duMNE/lXJ6/2SMeaMd7Xmx6/1O50SwzpjzBvGmH83m+cXWWv/xVr7Jdxk40bH2ATcCrw0ZdfDwHrg54EfLu3FMcY0GmN+wxjzvvee7DfGNHr79npXnjLGmOPFK7dmyvAPM2X4i/f7/VljzGHgsLftt7zXGDbGvGKMebjk+bXGmF8xxrznXRl7xRiz0fvb+Y0p5/i3xpjuWfze/tJa+1fAuRl2/xDwlrX2v1trc0AP8AFjzA5v/2eA37DWDlhrT+D+H4t5+zYDjrU2D3wTKA4f+r+Bf+dtn8oBvvdGMYtI9VJ7vSza61+11vZZawvW2peAbwEPXuMYaq+v2gx8yVqb83oRvwrc7u3rAjLW2n+0rr/HTYJvBVYCJ7yLoP+C1x4bY57wtvfOcCwHeMwY0zCLuJYFJWcL638A/iPwmLX2wCye/38CHzfGbJ+6w7hdxL+C+6V1Ne4Hyp9d43V+B/c/Riful9iZrux8H3Afbs/DJ4HvKtn3AHAUt+fhV4G/NMas8Pb9GTCA+8H0BPCfSxsD4KPAM0AI9+rHbwG/Za1tw/2P+qVrxPwsEPXuP+Id/9GSx9OuYFprH/HufsAbJlLsWenEvSq2AfhJ4HeMMR3XOC7gdtl7x/hta+2ve9v+X+9DdKbbG9d7veu4Ezg6Q4LwGeBvudo79H0l+34duBd4CLcX6X8BCl7D8Y+4PUGrca9mJecQy8dw3+td3uOXvddYATwN/HdjTNDb94vAp4Dvwb0y9hPACPAF4FPGmBqY6PF6DPgzY8xTxpi/m0M8pW4HXi8+sNZeAt7jamMwab93v7jvIPBhr8H8EPCWMeYHgUFr7bXmZ7yD+39BRJYntdfLrL32kqb7gLeucSi111f9Fm4i2mTcnrLvxk3QwB3Z8o4x5ge8xPBjwBXgDeAssNIY0wV8B2573AL8b8Avz3Qg74LrGDDt/9ayZa3VbQFuQAp3SNVfAzU3eG4UGPDu/1fgL7z7+4GYd/8fgZ8s+Zka3P9st3iPLbAVqMX7oy557n8C9pc8tsDeksdfAp7y7sdwe4BMyf5v43bhbwTGgdaSff8FSHj3e3DHZpee23PAZ4FVN/gdPAa84d3/KvBTQK/3+Fngh0rim3ouW6f8Li8DgZJtZ4A91ziuA3zOe78+dZPv+U/h9thc7zk/Ujyvkm1N3t/Kx7zHvwf8dcn7fBm3QZv6Wr8MfOU65/VTJY9n+r19+AaxXigeFzgEfPQaz3sH+A7v/s8B/zDH39t/Kv4NlWz7Q2DflG3Pl/x/GAd2lOzb5p2T8W77cBuGz+NeuUsCa3C/UD2HO0SjvuTnvwO3Efb9s0M33XRb2htqr4v7l0177b3eF7z4zTX2q72++nM7gVeAvBdPYsrf3U8CWW//CO6w4NK/l17vbyPivYc/6b3/3wT+CbhjyvFOAI/c7HtcLTf1nC2sfwPcBvyBMZOGIVzPrwHfZYyZehX/Ftyx0RljTAZ3rLPBvdpUajUQAI6XbDvOdKWTW0eAlpLHJ6z3v8PzPu6Vt/XAeWvtxSn7SmOYeqyfxP0d9Bl3yMb3MbMXgduMMWtx//P+MbDRu7JzP26jMVvn7OQrXVPPb6ofwf0geGYOx5ivC0DrlG0/iPuB9g/e4y8C322MWY17NTSI22s01cZrbJ+tSe+VN7TkHW8oRgb3auaqWRzrC8CPevd/lCnj8+cpi3vFr1QbcPEa+9uArL3qKWvtXdbaJ4GngP8G7PZujwL1uFcTi1pxhyqJyPKk9noZtdfGmP8LuAP45JTfXym11+6xanATqL8Emr3jdOD+/WPcYjr/FTfZqsdtY//AGBMBsNZ+3Vq7x1r7KFDAbYcT3rFjuD3WfzDlsGqTSyg5W1hncK8YPIx7pf6GrLXncItL/Mcpu44DP2OtDZXcGu30cfFncT84ukq2bZxj3BumNE6bcK/OnQRWmJLqd96+E6WnMOV8DltrP4Xba/FrwDPGmOapB7TWjuBelfl54KC1dhR4Abd7/j1r7eAcz2EueoBB3AmsE1WDjDH/zbhj42e6XWsYxI28AWwxkyf1fga3Meo3xqSB/w7U4Q5LGARyuENMpjp+je3gDpNpKnk8UxngiffKG6/+73GHzHRYa0PAEO4Xihsd60+Bj3pfUHYCf3WN583FW5QMM/T+Zm7l6vCTSfu9+9PeE2PMHbjDSz6PO0TlFa8hfhm3kEjRTiYPkxSR5UXt9TJpr40xn8Udlved1trh6xxL7bVrBe7f5W9ba694f/f/H+6wSXAT9OestQesO5fvZdx5eh8pfRHv7/S3gf8JN8Grtda+z5T22BizHjfJOzSL2JYFJWcLzFp7Evgw8Lgx5jdn+WOfw/1CubNk238DftkYczuAMabdGPOJGY43jnt1o8cbG7wDuFGp2KnWAP+TMabOO8ZO3K7v47gfwP/FGBM0xtyFe6Xti9d6IWPMjxpjVltrC1y9CjK1Mk/Rs7jd7MXx6s6UxzM5zdWCD/M1BnwC94rQnxTHY1tr/411x8bPdCvObypOvg3iXgGt8X43dTMdyFo7gDuh937vZzfgfiH4PtwPuAhuovFrwGe839sfAZ8z7uTuWmPMg8adKPtF3IninzRu+fiVxStVuMP4fsj7G9iK+z5dTyvul4SzQMAY838wuWfqD4D/aIzZZlx3GWNWlpzTy7hXwb5srb18g2MVf28B7/dWC9R6v7diI/gV4A5jzMe95/wfuMNo+rz9fwz8ojFmg/dB/ku4V+JKX9/gzuf4ee/3eAzYa9y5aI/izpMoehR3KJKILFNqr5dFe/3LwKdxh/bNVIxqgtrrid/DIG77+T94sYdwk9TiBc2XgYeL52OMuRv3IsfUuX4/BbxmrU3iFgJrNMbswp0bXtoeR4FvWGuv3Ci25ULJ2SLwPiQ/DDxhjPkvs3j+MG4X8YqSbV/B/QD4c+NWVjqIe+VnJj+H28Wdxv0P+Ge4kzNn6yXcOTyDuHN0nij5EPsUEMa9KvcV4FettV+7zms9jjsBNIs3odS61fdm8izuh85z13g8kx7gC8YdPvLJG5zXNXlX/n4It6H7o+IH/iz9GO4489/F/UC6DPz+dZ7/e97PFH82aa39Z2ttunjDrSx4l9fz8++AN3E/AM/j/h3UWGv7ca9c/ZK3PcnV3qTfBEZxG8MvcJ0G2fNPuMnJu7hDX3JMHkbxOdy5Dv+MO97+D4HGkv1fwO2ZmhgiYdxqUddLeP433N/VU7jDKy5727DWngU+jvv3dwF3IvQPl/zs7+FOyH4T9//C33vbSv047lXd4uT+v8T9uz2LOw/t97w41+FOsv6r68QqIsuA2uuqb6//M24P4uGSnrVfuc7z1V67fgj37+MscAQ3OfwFAOsuOdGD29N6Efgy8J+ttRMLkBt3yOvP4y6PgzeU9eeAb+BezPi3Jcf6EW+beMy1h95KpTLG/BrQaa39jN+xCHhX0V7DrQp2yu94FoIx5hHc4RJh7+phxTBuaeH3rLWzGsokIrJY1F6XF7XXS8sYcyfweWvtjMsbLFdKzqqANzSiHvfqzX24E1d/yrprSoksKG8I558Dr1tr/4Pf8YiIVAq117KU1F5XJg1rrA6tuEO4LuF2bf8GbolgkQVljNmJOzdhHe7EeBERmT2117Ik1F5XLvWciYiIiIiIlAH1nImIiIiIiJQBJWciIiIiIiJlIHDjpyycpvYmG+oMLeUhRUSWrVPvnhq01q72Ow4pf6uammw4FFqag507R3LFKNTWsqZ5zdIcU0SkjFyvfV7S5CzUGeLJ33tyKQ8pIrJsffZDn33f7xikMoRDIQ48uYTtcyJB+IkBMqtG6N7TvXTHFREpA9drnzWsUURERJZWLEbqmS7IXWvNYxGR5UnJWRWy1jJ0eoj+N/s58c4JRi+P+h2SiIjIjJyU43cIS+ryxcscf+s4/W/2kz2f9TscESkzSzqsURZffjTPK197hVODp7ArLSZvqHmhhsieCJtu3+R3eCIiIq5wmFB2gGSqF4BoOOpvPIvMWsvhlw/zzpvvYFdbMMAB2BzezJ2P3ElNra6Xi4iSs6rz9vNvc3LsJKFHQhhjAMiP5Hn126/S2tFKx/oOnyMUEREBolFSDkR39JKk+hO0U++e4uC7B2l/uJ3a+loA7LjlvQPv0ZxsZuu9W32OUETKgS7TVJHRy6OkjqZov719IjEDCDQFqA3XcvTgUR+jExERmSIaxflqJyGCfkey6A6/eZjG2xonEjMAU2tovb2VwwcPYwvWx+hEpFwoOasiuWwOglBTN/1tbVjRwNCFIR+iEhERuYFcjlQm5XcUi2o4M0zDioZp2+ta6hjNjzJ2ZcyHqESk3Cg5qyINzQ3YnKWQL0zbNzo0Sktbiw9RiYiIXEcsRjgDmcEBEsmE39EsmubWZkaHphfoyo/kCdQECNRrpomIKDmrKg1NDXRt7GL43WGsvTo8Ynx0nLFjY2y5fYuP0YmIiMzM6XyK7oMtZDLpqq3euO2ObYy8O4Idv9o+24JluG+YW3fcqoIgIgKoIEjVufPhO7n095c413uOmlU12DELp+GOO+5g5caVfocnIiIyo55kiEQk43cYi6ZrZxfnz5zn2P5jsBZMjcGetmxYsYFtu7f5HZ6IlAklZ1WmvrGevT+4l3PHz3Hu1Dnq6uvofLCT5o5mv0MTERG5vmyWZDpZlVUbTY3hruhdhM+GOZM6g7WWVbevomN9x6QiXiKyvKkPvQrV1NawOryaHQ/u4NZ7b1ViVoYK4wUK49PnBoqILFuxGLEjLTA8TLw37nc0i8IYQ/uadrbdv43bHriNFRtWKDErM7Zg1T6Lr9RzJrKEhs8Oc+jAIU4ePwnA+k3r2bF7B62rWn2OTETEfz2RbnoSCUIxd+5ZNfagSXkavTzKuy+/S+rdFPnxPB0rO9hxzw7Wblnrd2iyzKjnTGSJDJ8d5rm/e450Y5rWD7fS+uFW0sE0z/3tc1w8d9Hv8EREysZyWPdMykd+NM/zf/M8Ry4eofHhRtq/s52RTSO88OwLDPQN+B2eLDNKzkSWyKFXDmE3W1rDrdQEaqgJ1NAabqUQLvDuK+/6HZ6ISPnIZkmmequ2cqOUlxOHTpCpyxC6PURtQy3GGBrXNNJ8bzNvvvSmhjnKklJyJrIECuMFTvafpLlr+vy/5o3NDBwbmLT8gYjIshWLkXqmi1A2rwRNlsTAsQGCXdN7a+vb6hmtG2X47LAPUclypeRMZAlowreIyBwUEzQNbxS/6bqpLDElZyJLwNQYNmzawKXjl6bty/Zn6drcpQRORGSqXM7vCGQZ2Lh5I7nj0//WRodGaRhvoG11mw9RyXKl5ExkiWy/bzs1qRqGjw5TyBco5AsMHx2m9v1atu/e7nd4IiLlJRwmnIHkkf0kkgm/o5Eqtn77ejrGO8i8mSF/OY8tWEbSI1x69RJ3PXAXNbX6uixLR39tIkukdWUrj370UTbkN5D9RpbsN7J0jXfx6EcfpWVFi9/hiYiUl2gUp28PkcEAmcEBJWiyaAL1AR76/ofYvmI7V168wtDXhmg71cbDjz3M+u3r/Q5PlhmtcyayhFpWtHDvd97LPfYeQHPRRESuKxrFIUpPMk78DjdBi0VifkclVai+sZ6dH9zJjod2gHWnI4j4QT1nIj4wxigxExGZpZ5IN90HW9SDJovOGKPETHx1w+TMGBM0xnzbGPO6MeYtY8xnve0rjDFfM8Yc9v7tWPxwRUREBJZf+9yTiRDJagi4iFS32fScXQE+bK39ABABHjfG7AGeAr5urd0GfN17LCIiIktj+bXPuRyZXMbvKEREFs0NkzPrynoP67ybBT4KfMHb/gXgY4sRoIiIiEy37NrnaBTnq50wPEy8N+53NCIii2JWc86MMbXGmCRwBviatfYlYK219hSA9++aa/zsk8aYA8aYA2fOniGRTGi8uIiIyAJYqPb57MjIksV8U2IxMk9vIpTJ6buEiFSlWSVn1tpxa20E6ALuN8bcMdsDWGs/b63dba3d3VgH4VRGE3pFREQWwEK1z6ubmhYtxgUXDhPOBf2OQkRkUcypWqO1NgM4wOPAaWPMOgDv3zM3+vntI404ycikikvqSRMREbk5N9s+V5xcjkwmjZNy/I5ERGRBzaZa42pjTMi73wh8BOgD/gb4jPe0zwB/fcOjtbZCNDpREjfclybclyZzpl/jx0VEROZgQdvnSuItTh3K5kmmepWgiUhVmc0i1OuALxhjanGTuS9Za//OGPMi8CVjzE8C/cAn5nLgnkj31fvJOPFd7gTf7j3d1/wZERERmbAo7XNFiEZJORCNJEllUn5HIyKyYG6YnFlr3wDunmH7OeCxhQiiJ9JNTyJB6NP9StBERERmYSnaZxERWVqz6TlbGrEYmUSC8BMDxJ19EHQn+0Y6I0TDUX9jExERkfKTy03MYY9FYn5HIyJy0+ZUEGTRxWKknumiOxmkuxdCg1mNJxcREZHpolGczqeIDAZUBVpEqkb59JwVxWL0eHd7HIfw7v0kU70A6kETERGRSZy+Pe7cs1V+RyIicvPKq+dsqmiU1IG9RNKQPLJfPWgiIiIyXS7ndwQiIguivJMzmCiZGxkMkDyyn7izj7izT8MXREREBKJRoumgluURkapQ/skZTIwrz/xpF5lEJ91J90NYCZqIiIj0RLrpfrsNhof13UBEKlplJGdFsZg7J837ENZVMhEREQE3QYucr/c7DBGRm1JZyVmJ0qtk8d44TsrRnDQREZFlLpPL+B2CiMi8VWxyBm6Clnl6E6HBLKm+XndOmnrSREREliXnq52EBrPueqkiIhWo/Erpz1UsRspx3Pup1MQi1qFQJ+FQGFAJfhGpHsNnhzned5yLwxdp72hn085NNHc0+x2WSHmIxUglEhPfBSLhPfoOICJLIpfNMdA3wLkz5wg2Btl420Y61ndgjJnT61R+cgYQjU7cTSUSRB9PQyZDKthLJug9RR/OIlLh+t/q59Vvv0pNVw2BlQFOZ05z+CuHeSD6AGu3rPU7PJHy4F201TqpIrJUhk4Psf8f9pNfk6duZR35kTzH/uUYO27bwfY92+eUoFVHclYqFsMp9qQB0R29JPP73fv6cBaRCnV5+DKvvfQaLXtaCDR5H92dMLpulJedl3m863EC9dX3kS4yL9EoKcf7DhBMqv0XkUVjC5YDXz+A2Wlo72yf2F7YWKDvhT7W3rKWjvUds369ip5zdk3R6MStdI00ldcVkUp16r1T2DX2amLmqW+vJ9+e52zqrE+RiZQpb/0zEZHFNHRmiIv2Ik2dTZO219TVULOxhv5D/XN6vepMzkqVJGiZwQESycTETUSkUly5fIWaxmt8ZAdh7MrY0gYkUimyWbX5IrJoxnJjmODMwxYDTQFyl3Nzer3qT85gYhHr7oMthPvShPvSWsRaRCpKx5oOCucL07Zba+E8tK5s9SEqkfLWE+medHFWRGShtaxswWYshfz0Nnr07Cgr166c0+stj+TM0xPpxul8yk3UtIi1iFSQ1eHVtI61cvHoRTchwx3nPnxomFXNqwitC/kboEiZKl6c1fpnIrIYGlsbCYfDDB0cmkjQrLWMpEeoP1dP1/auOb3eskrOSk1dxFpEpJzVBmp58HsfJJQJMfTcEEOvDDH07BBr82u57/H75lyqV0RERBbGnY/cyebWzQw/O8zwK8MMPz9Mw7EGPvg9HyTYMre5r8u6tFdPpJueRILQpyf3oHXv6fYtJhGRa2lqb2LvD+4ley5LLpujqb1Ja5yJzJZ3MVZtvIgstNq6WiKPRdh+cTvZ81nqGupoX9s+rwuny7bnbEIsRubpTXT3QncvhAazxJ19OCnH78iqXmG8QCad4fyJ8+RH836HI1IRjDG0rmpldXi1EjORWdJombmx1nJx8CLnBs5x5dIVv8MRqRiNrY2svmU1oc7QvEe0LOueswmxGD3e3Z5EgvATA1q4cpGl30uTfD7JldorUAuBywF23b2L8AfCGp4lIiILrifSDck48T1+R1LesuezvPKNV7hw6QKm0cBFCG8Jc8feO6itq/U7PJGqp+RsqliMlOMQ3r1fCdoiuXDyAr3P9dJ4dyPtIXexvvxIntdeeY1AfYCNuzb6HKGIiMjyM3p5lOf/7nnGNo/R3uUOySrkCxx98yiFZwvc/ZG7/Q5RpOppWONMolFSB/YSSUPyyH7izj7izj6V4V0gh5OHCdwaoCHUMLEt0BSg+c5m3nn1HWzB+hidiIhUq55kSNMXruPkuye53HaZlo0tE6NYagI1hO4K8f777zMyNOJzhCLVT8nZtXiLV2f+tItMopNImol1UpyUow/1m3A2fZbGtY3TtjeEGhi5MsJobtSHqEREpOrFYqSe6SKUzZNMJ/2OpuwMnh6kbnXdtO2m1mA6DBfPXfQhKpHlRcMarycanbjrAD3JOImtA6QyGTLkSKaTqvo0Dw3BBsZz49Q2TB67XhgrUFOooTagMe0iIrJIYjFiyTjxVX4HUn6K7fOMrkCgXl8bRRabes7moCfSTeqZLlKJEN3JoKo+zdPm7Zu5dOTSxEK6RRePXaQr3KUPfxERWXy5nEbBTNG1rYvCQIHCWGHS9txgjuBYkI51HT5FJrJ8KDmbq1jMre6osrzzdsudt7C2di2Zb2cYOTXC5dOXySQztAy2sOvBXX6HJyIiVa4nE5mYV6755FeFOkNs37adoReHuPj+RXKDOYb6hhh7c4z7HruPmlp9bRRZbOqiuAlTF7EOBUMAxCIxX+Mqd4H6AA983wOk30tz/MhxCoUC67esZ8NtG6gLTh/rLiIisqCiURwHojt6SQbSfkdTNowx7HhwB2s2ruH9Q+9z+cRlwmvCbHpwE03tTX6HJ7IsKDm7WbEYmUSC6ONpCGZIBXPEnX1EwntUgv86agO1bNi+gQ3bN/gdioiILEfRKE4iRSim5KyUMYaVG1eycuNKv0MRWZaUnC2EWAzHcSYeao00kfkpjBc40XeC1LspRq+Msnb9WjbfuZnmjma/QxORapXPk0gmNOpF5DqstQz2D3L04FGyF7O0hdrYcscWVnYpiV9oGjy8UKLRiVvpGmmabCwyO4XxAi//48u8fPBlshuyjO8a573ce3zzr77JhVMX/A5PRKpRLEb3wRYyZ/o1f1zkOo4cOML+Z/cz2D7I+K5xTjed5rl/eY5jrx/zO7Sqo+RsMXhrpEUGAxOTjYs3EZnZqcOnOHHpBB33d9C4ppH6tnrab2unZmcNyeeS06p7iogsBBX4Erm+S5lLvP3m27TtaaO5q5n6tnpaNrXQ+kArbx54kyuXrvgdYlVRcrZYShK0cF+acF96YhFrEZnu/cPvE7wliDFm0vbGtY0M5Ya4dOGST5GJSLVTgiZybaePncautdTWT16HNtAYoLCqwNn3z/oUWXVScraYolGczqcmbsWhE0rQRKYbGx2b9sEP7uR0U28YH7vGwqgiIgugJ9JN5ulNWv9MZIr8WB5TZ2bcZ+us2ucFpuRsCRWvzGlsu8h0nV2d5E7lpm3Pj+QJ5AIqCiIiSyJE0O8QRMrKis4V2LN22vQCay1m0NC+tt2nyKqTkrMlpqETIjO75fZbqD9bT7Y/iy24DcDYpTGGXxtmxwd2EKhXcVkRWQLZLMlUL/HeOPHeuHrRZNlb2bWSVU2rGHpriEK+AEBhrEDmjQzrVq5TcrbAlJz5YGLohBI0kQnBliB7v38voXMhhp4dYmj/EGMvjxG5PcKWu7f4HZ6ILAexGKlnuuhOBunuhdCgm6gpQZPlzNQYHvjuB7il8Rayz2YZen6I7HNZbm2/lXu/495pc8Xl5uhStF9iMbqTceJ7/A5EpHy0rmxl7w/u5fLwZfJjeZram6gNTJ+HJiKyaGIxery7PY5DdEcvyfzV9UuLQqFOrY0my0ZdsI67H7ub2y/fzpVLVwi2BKkL1vkdVlVScua33PQ5NlLdrly6wvkT5wFYsWEFDc0NPkdUfhrbGv0OQUTELezlAKnU5M2Pp0nmB7R4dZUZHxvn3MA58qN52la30bKixe+Qyk59Yz31jfV+h1HVbpicGWM2An8MdAIF4PPW2t8yxvQAPw0U62f+irX2HxYr0GrUkwyR2DpA3NlHJLyHaDjqd0iyiKy1HH75MH1v9mFXWCyWmm/VsPOunWzdvVXDAkRkTtQ+L5FodNomB+hJxonv6leCViVOHz3NgWcPMNYyBvXAC9C1rovIhyOa8yxLajZzzvLAL1lrdwJ7gJ81xuzy9v2mtTbi3fTBP1exGKkDewll89OGS0j1OfHOCQ6+e5Dmh5tpv7ud0N0hmvc28+ahNzl56KTf4YlI5VH77CNVYK4e2fNZXnr2JeruqSN0X4jQB0K0P9rOQG6Ag/sP+h2eLDM3TM6staesta969y8C7wAbFjuwZSMaJfVMl99RyCKz1nLo9UM072qetJZXbUMtTTubOPT6IR+jE5FKpPbZf6rAXB3ef+t9bJelvv3qcD1TY2i7o433j73PlUtXfIxOlps5VWs0xoSBu4GXvE0/Z4x5wxjzR8aYjoUOblnJ53FSzsRNqostWC4OX6S+Y/o47YYVDQxfGJ4oHy8iMldqn/2jCsyV7/zgeRpWTJ//XROogRYYGRrxISpZrmadnBljWoAvA93W2mHgd4FbgQhwCviNa/zck8aYA8aYA2dH9Mc9o3CYyGCAVF8vqb5ekkf2k0gm/I5KFpCpMdQ31JMfyU/bl7+UJ9gYxNRozpmIzJ3a5zIQi5F5ehOhwSxxZ5/f0cgcNbc0M5Ydm7bdFix2xFLfpAIYsnRmlZwZY+pwP/i/aK39SwBr7Wlr7bi1tgD8PnD/TD9rrf28tXa3tXb36qamhYq7ukSjOJ1PkerdQ6p3D90HW8iccScZF29S2YwxbN21lYuHLmLt1R4yW7BkD2W5ddetPkYnIpVK7XMZ8dZIC2XzxJ19GgVTQW7ZcQv5VJ7CWGHS9mwqy+qO1TSHmn2KTJaj2VRrNMAfAu9Yaz9Xsn2dtfaU9/AHAc2YvFleRageopCM45xPQzBIsiVLvDdO955uP6OTm3Tr3bdy/vR5Tr14itpOd95Z4VSB9aH1WmRZROZM7XMZisVIOQ7h3VfXRVMl5vK3omsFt++8nbf3v41Zb6gJ1jA+OE5LroW7v+9uv8OTZWY2tUE/CPwY8KYxJult+xXgU8aYCGCBFPAzixDfstUT6cZdXAV6Qkniu9yx7KFgCEBleytQbV0tD3zvA5wbOMep1ClqTA1rH17Lyq6VGtIoIvOh9rkcRaOkHCYWrwYlaOXOGMNt999G5+ZOTh45yeiVUVbsWkHnrZ3XLaOvZRRkMZjSIVaLbff69fbAk08u2fGqSiJB9PE0AKmWPJmWAN3Rp3wOSkTK2Wc/9NlXrLW7/Y5Dyp/a50XgOG6CtipPaFWXvsRXmXhvHLJZCAS0Vq3M2fXaZ62qVyliMZzi/USC8BPu4tWhUCcA4VC4Kj8YCuMF+g/2c+StI4xkR2hf0c5tH7iNzq2dWrRZRETKVzSK43g9aAxUZS/LmWNneDf5LufPnifYFGTrrq3cctct1AZqb/zDFcZJOaQyKQAymTShbJ7UM12EnxjQEFZZUHMqpS9lwlu8OpKGcF8aBtwPhmqbfGyt5bV/eY1X+15lfNc4LR9uYWTTCC+++CJHXz3qd3giIiLX5xX8igwGyAwOVFWBr/fffJ/nn3ue4XXDtHy4Be6E5NEkB/7pAIXxwo1foII4KcdNwAYGCPeliaRx16j1vo+Fsvmq/B4m/lDPWaWKRnGIuveLQyfy+0mmkwCEgqGKv0J34eQFjp85TscHOybmZDWuaaS+vZ6D3zpI184uGpqmr0siIiJSTpzOp+hJxonv6q+KHrSxK2O88e03aH2wlUCT+1Wyvr2ejns6ONl7knPHz7E6vNrnKG9OIpkgk8u4D7JZIoMBnL69E8XbiHlPLM4xjCQnetZEboZ6zqpBNIrT55bg7+6FSCpXFVfo0qk0Zp2ZViyjtqEWVsK54+d8ikxERGRueiLddL/dRuZMf8UvVn3h5AUKbYWJxKzI1BgC6wOcPHbSp8gWRiKZIDM4QCSVo7sXug+24PTtuZqYiSwi9ZxVi2jULcHvqYYrdNbaa1YxtGbpCtmIiIgshJ5INyTjExWYiyptqRxr7TUv75saM229sEowY09Z51PQOcsXyF29MF6p37ukPKjnrEpVwxW6NRvXMJ4eZ2pF0cJYAXPO0LG+w6fIRERE5qcn0k3m6U1uj0wvhAazxJ19foc1Jx3rOjAZw/iV8UnbrbXkT+VZd8s6nyKbn3hvnMyZ/on3pPtgi5uYzVYVzy2Upaeesyo29QpdpV2ZW7VxFZ0tnaRfT9O6vZVAY4DR4VGyb2XZvmM7ja2NfocoIiIyd7EYPd7dnpIKzEXlXpq9vrGeHXfu4OCBgzTf3kxDqIHx3DjDh4dZFVjFms1rJj0/3huHXO6Gr7uU5z0pptFRut9uc7833YRqm1so/lByVuUqOUEzNYb7Hr+PwwcOc/TFo2QLWRobGrnnrnu45c5b/A5PRETk5sVipBwHUimAiinNvu2+bQSbg/S91kcmlyFgAty2/TZuu+82amrdgVnFKofFsvPXs5TnHe+Nw/Awmac3Xd0Yiy3Ia09870IJmsyPkrNloCfSffXKXIUlaIH6ADsf2sn2B7Yznh8nUBe45jw0ERGRilRSaCJVWoHZS1ZCoc6y+5JvjGHT7ZvYuGsj+dE8tYFaamprrpad94SyeVIH9kIset3XSzkO4d37FyVBmzGmZzYtWEI2VU+kGye9j9SaGz9XZColZ8tFLEaqZOhEuQ+ZmKqmtmbiSpyIiEjV8havLvakRR9Pk8y785jCobC7rYzab2MMz596fuJx8sh+t5jGV71KGuHw7KocFkvSe4nppF3zON/SNcdm7L1bpMSs1ESBEZE5UHK2nJQkaJUwZEJERGRZKklmHNwKzImtA6QyGTLkSGVSZdOTlkgmyGTShAhCLkckE3DLzt+gp2xGXmIa3dFLKt8LweC8znd6TLhrlM0npnlyvtpZkSOWxH9maiW8xbR7/Xp74Mknl+x4cg3e0IFMS6DietBEZPY++6HPvmKt3e13HFL+1D5XgEQCgJ5IhviuYWhrI9IZAZbuQmtpbxRAKpNyqxy+3UZPMuRuXKgeqSnnG1qz6bo9h8XYUpmUu0bZfHrvFpp3QTyzqkUJmkxyvfZZPWfL0QxDB5SgiYiIlDEv6ekBSMZJbM2SyvSSCeRJppOL/uU/3huHbJZQvuSrYz5P9xGvymFkgQ849XxHB0il0zOeb3HR6GJskYy3RllsgWOaq1iMWDJOfJXPcUhFUXK2XJUMHUiyv6yGSJQTJ+UocRURkbLSE+mmx3HcB6nUxHzyUMjtKQqHwgvSdhXX68rkMlerG4bDk5+0BD1SpefbE0pOVKAOBUMTsXW/3UZPJrJkMc1JLqfvEzJrSs6Ws2gUhyjR9D6SaFX7UhOVnfJLc0VSRERkTkorPCYSRB9PQyZDKpgjmUm7T5lnMjBRAj8H4Zw7b8v56uJVN5wV73x7iNJTPN9gBnI5oumbX6NssfRkIjjpXpJorr/MjpIz0aKJHiflkMqkANyJxNk8sSMtk67QAcv29yMiImUqFsMp9qTBREn6Yps2m560mdrA1DNdV3vKlrCYxg1NOd+y6ykrVRyphDuVRCOV5EaUnAkwedHE5VhZqDhePTJ49b+E07fX/cBPxnE6c0Ca5IrRZfn7ERGRMjdprTR32gJptwctuWrgukmBk3ImSuBPbFvi6oZzVs4J2VSTppJopJJcn5IzmTCRoHk9RdWegBTH0gNXKzv17bn6ge8VeZo0VKJkrbiFHtsvIiKyILxpCxMPS6YvzOR6baAskNKpJC0Zv6ORMqZVfWWSnki3O+F32E3QqlUimSBzpp9wX5pwX5rugy1uZacbXYmLxUg900UkDeG+NAy4a8ZNLS8sIiJSLpzOp+g+2DLR5k29zboNlJsWTQf9DkHKnHrOZLpYjExJD1F39Cm/I1oQk5LNYmWnYq/YXK4QxmI4xfuOoyUJRESk7F23YIZ6yZbW8PIYoSTzo54zmZnXQxTK5ok7+yq+ZyjeG3cTsl7c29sLVNkpGsXp20NkMEDyyP5rDhkRERER6Yl00/12W9WPUJL5U8+ZXFssRsrrQUumKq8E7NSesszTi1QGeMpE3+JxQ8GQJvyKiIjIJBNz/Pf4HYmUIyVncn2xGKni0L0KWaNjYn0WrxQ+QE9ykddn8Sb69iTjE5uW+9IEIiIiIjI3Ss7kxipgjY6JRaM9oWye1IG9Vyc3R5YmjklDJYtLEzj73MfBoMaXi4iICD3JEImt1TW3XxaG5pzJ7JTMrcoMXrscrx8SyYS7PksaMolOMonOyYmZT4qVLzOJTrqTQY0vFxEREVeVze2XhaOeM5m90jU6fF5EMZFMkMmkCRGEXI5IxlufpdwWzPSGUvYAPcUKmKrQJCIiIhU+t18Wh3rOZM6K66VkzvQvaQ+ak3JwUs7EGmXdySCpRIjUn3dWxvosxatkg9mJq2TFm4iIiCxDsRipA3uJpJk0PUOWL/WcybxMVBqif0l6guK9ccjl3J6ybJbuI14p/MiiHnbhlVwlS6WSAGTIAbpaJiIisixFoziJFKFY2u9IpAxUZHI2fOUKr544wdmhIdqamri7q4s1zc1+h7XsTCRouxZnMcVij1Iynby6aHQyBIQWt/LiYvMqYJJKARB9PD2xiHWREjURqUSj4+O8kU6TOnOG+vp6bl+3ji0dHRhj/A5NRKQiVFxy9t7583z5xRe5Y2yMHYEAZ8fH+UJfHx+69152d3X5Hd6y0xPppieRIPTphe1Bizv7CLkdSoTyeVLPeKXwIwvy8v4rGYLpeEsVpPLucIZMIF+WFTFFRK5nKJcj8cILrB0eZmcgwOVCga8ePsy6LVv42J13UqMETUTkhioqORsbH+cvv/1t/lVtLbeU9JTdPTbG77/yCltWrmRFY6OPES5TsRiZYrGLeZaEdVIOqUwKwC30kc2TeqYLwmHvGNEFC7fseIVWcBz3obeYtdZIE5FK8ndvvsk9Fy/ycCg0se3eQoE/PnKE11ev5u516/wLTqScOQ7RxzWkUVwVVRDk0LlzrMvluCUYnLS9o66OiLUkT570KTK5mZKwxTXKwqkM4VSGSBq3FH4s5vYwlXuhj4XinatfBVdERObr4pUrDJw8yZ7W1knb62pqeDgY5LVjx3yKTKTMeaNnkqvyhEKdfkcjZaCies6yo6OsvMa+lbW1nLh8eUnjkSm8uVTh3ftvWBK2NOnIDA4QGQzg9EWuPmG5JGTXMLXgSigYAlBPmoiUpUtjY7ThJmNTrayrIzsysvRBiVSCVIpkFCLhvZpvLkCFJWdrm5t5DbDWTptcnBofp6u93Z/A5KpolJTjDc3zilxM/bBJJBMTCZnLW6NsmSdkUxUTNKczB6RJrhjVGmkiUpY6gkGGamvJjo/TUls7aV8ql2Pthg0+RSZSAYJBJWYyoaKSs3AohFm5kv3nz7O3rW0iQXvn0iWONTbyvRrPXh6iURynOHdq/8RcsqLMmX638mKk++pG9eTPaNLvqGReX3HoQzgU1ge6iPiuIRAgsnUrf/vOOzzR3j7RgzY4NsazhQIf37LF5whFRCpDRSVnxhg+dd99fOmVV0iePctGYzhrLZdaW/n0/fcTDFTU6VQ3L0HrCSVxOq9Oco2mg8CUxExmx1sjrSeSwelMk2rJk8y4v1slaCLit4/cdht/OzrKbx49ylZjuAwMBAJ81/33c0tJkRAREbm2istm2oNBfuqhhxgYHmZwZIQ7GhrY0tGhEr3lKBqlh+jkbeohuzmxGD3F+7Oc3ycishQCNTX84F13cX7bNvqHhqirqeGJFSto0IVTkZl5I2Kgxe9IpIxU5CemMYaN7e1s1BwzmaeCtZzOZrG4cxlrZ5jEXvZmMb9PRGSprWhs1LI2clPOjYxwOZ9nVVNT9Y6K8taIpa1Nc8llkhv+xRtjNgJ/jNvnUQA+b639LWPMCuAvgDCQAj5prb2weKGKLIy3z5zhn19/ncClS9QAlxsb+fCdd3L3+vV+hzZ3U+b3JdNJAELBkCo7ilQ5tc9SbU5ns/zt668zdPYsbcZwrqaGu2+7jY9s21aZF1GvoyeSUWImM5rNX3oe+CVr7U5gD/CzxphdwFPA162124Cve49FytrRCxf4xxde4OPj4/xcKMT/GArxI8bw7Esv8dbp036HNz8la6N190J3L1ojTWR5UPssVSM7OsqfPP8895w/zy+0t/PT7e38XFMTZ99+m6/29fkdnsiSuWFyZq09Za191bt/EXgH2AB8FPiC97QvAB9bpBhFFsxzhw7xXXV1bCxZyLyzvp4fCAZ5rq8Pa62P0d2cnkj3xK377TYyZ9w10kSkOql9lmpyYGCAHZcvc09r60QdgZbaWp5ob+fNI0fIjo76HOHC6kmGCA1miTv7/A5Fysyc+oiNMWHgbuAlYK219hS4DQSwZsGjE1lgx8+cYfsMcyE2B4Ocv3CB0fFxH6JaeMUEjeFh9aCJLANqn6XSHT9zhu319dO2B2tq2GgtJ4aHfYhqEcVipJ7pIpTNE3f24aQcvyOSMjHr5MwY0wJ8Gei21s76f4gx5kljzAFjzIGzIyPziVFkwdQHAowUCtO2X7EWamqqZ0y747iLV9fUEA6F/Y5GRBaR2mepBvX19TO2zwCXgPopi5tXhZIELZnqVYImwCyTM2NMHe4H/xettX/pbT5tjFnn7V8HnJnpZ621n7fW7rbW7l7d1LQQMYvM2x2bN/NCNjtt+0sXL7J90yYCVZKcRXf0kuyEyNa9quAoUsXUPku1uKOri5fGxhifMr3g/VyObGNj9a6VF4uROrCXSBqSR/bjpJyJmyxPN/wmaowxwB8C71hrP1ey62+Az3j3PwP89cKHJ7KworfeypH2dr5y4QLv53Icz+X4+0yGV5ub+ciOHX6Ht6BCoU4lZiJVTO2zVJOdq1cTCof5QibDoZER0qOj7B8a4ktjY3z/vfdW93q20ShO3x4igwFSfb2kUkmSqV5NS1imZrN4xAeBHwPeNMYkvW2/AuwDvmSM+UmgH/jEokQosoCa6+v5qb17eXlggH86fhxrLdu2buWnN22iZYax7iIiZUzts1SNGmN4IhLhjXXrePHYMS5fucL69ev51+Ewa1uWwSLN3tI4pFLuw8fTJEnjpBxdaF1mbpicWWv3A9e6XPHYwoYjsvga6+p4ZPNmHtm82e9QRETmTe2zVJsaY4h0dhLp7PQ7FH9EoxN3nUSCcCzjWyjinypddn15G8rleKm/n/7Tp6mvq+OOW27hA2vXVk+xCxGfZdIZUm+lGB4epq29jfCuMKHOkN9hiUiZGx0f59WTJ3nn+HEKhQJbN2zgvq4umurq/A5NyoXjAO4i1Rly/sZSgUaGRuh/u5+z6bPUN9QT3h5mzeY1mJrKGRar5KzKnLp4kT/dv58PXLnCdwSDXC4U6D11ire6uvjUvfdWTcELEb+8/+b7vHbgNWpuqaHhlgYymQypf0xxz/33sOn2TX6HJyJlKpfPk3jxRToGB3k4GKQWePP11/m9997jx/fuJVSy/qYsQ45DdEcvqT3uw0wgTyjUpSGNc5BJZ3j+H58n35mnYVMDw7lhTr50knAqTORDkYpJ0JScVZm/e/11vnN8nA+UVDW6rbGRPx0Y4LV167ivq8u/4GRJ9CTjJO/IE/I7kCqUy+Z4/duv0/JQC4FG9+OzYUUD+c48yReTrA2vpaG5wecoRaQcfevYMdYNDvIDoRDGK26xubGRZ4eG+FpfH5+IRPwNUJae40yeY7YqT2Tr3ondSsxmz1rLq86rmJ2G9s72ie1N65pIvZhiw/sbWLO5MpZ8VHJWRc6NjDA8OMid7e2TttcYw0PBIM+mUkrOqlxPMk581zC0tBGLxPwOp+qcPnqawurCRGJWFGgKUFhV4MyxM2y8Y6NP0YlIOXvj6FE+09IykZgVPdDayuf6+xm7807qqnEtL5lZIkH4iQGIusVOMkAkrOVv5uvi4EWGx4ZpXzv5O7CpMdRtqqP/UL+SM1l6uXyeFmNmLDfbUlvLlbExH6KSJeM4ODty0NZG955uv6OpSmOjY3CNjjFbb939IiIzyI2O0trcPG17gzHUFAqMFQpKzqpdIjFxN/zEAJmWAJFwZGKbErP5y4/mMfVm2sUPgNpgLVfOX/EhqvlRclZFVjc3kwkEGMrnaQ9MfmsPX75M14YNPkUmSyYYJBQM+R1F1QqtCcG77vCJ0gbAWos5b2i/s/3aPywiy9rGNWt49+xZ7pxSFn7gyhWaWltpDOgrWVVLJAh9uh8mlu0J0B19yteQqknLihZM1jA+Ok5t/eSLHFfOXGHNusroNQMlZ1WlvraW+7dv58tvvMEn29tpqa3FWst7uRwv1tYSC4f9DlEWQU8y7t4JQbIlS0izzRbNyq6VrKhfwYW+C7Td1oapNdhxy9C7Q6xqXMWKDSv8DlFEytTe227jK6dOsfLKFdY3uF3w58bG+OvLl3n4rrtmvOIv1aMnktHIlkVU31jP1p1b6Xutj/ZIO7UN7nfgkZMj1J+tZ+OjlTPlQMlZlXn01lspWMtvHzrEmvFxRqyl0NrKJ+65hzUzDKeQCuZVdkrekQfvSmwo2KW5ZovI1Bge+J4HeOPZNzj57EloBi5B1/ou7vpufbkSkWvb0tHBdz34IH/++us0DQ0RAM7X1fHIvfdy9/r1focnUvF2PLCDGlPD4f2HKTQXsFcsoaYQ93zvPQRbKqcaqpKzKlNjDI9t28YHN2/m1MWLNAQCrJthArJUKMehJ5R07+7ITVR20jj1pdPQ1MB9330fly9eJncxR7A1SGNro99hiUgFuGPtWnZ+5COcvHiRgrWsb23VPLNlYKJYF21+h1LVampr2PHgDm69+1ayF7IE6gPucMcK+w6s5KxKBQMBNnd0+B2GLCSvslOmJQDBIBAk0hlRYuaTxtZGJWUiMme1NTVsbNf81OWimJiF1mzSyJYlUheso2Nd5X4HVnImUs4SCXecOpB4IutVdtqjhExERKRStGl5G5k9JWci5apY2amtOAyiRROJRURERKqYkjORMtKTjON05gBIfnpUlZ1ERERElhElZyJ+cxwAekJJd8JwWxuhoFsQX8MgREREKpTj4OzIAZVTKVD8p+RMxEfR9D6IuB/ayZYsoVWaMCwiIlLxisvddEKkM+J3NFJBlJyJLCWvlwxwP7RX5QmtCgEQIqTETEREpApMJGYq4iVzpORMZKl4V9FSIfdhJqA1ykRERKpVKNSpNl7mTMmZyGIq9pSlUhNrlEXCeyZ260NbRERERIqUnIksFm/RaAIB2AOZoNYoExEREZFrU3ImspASiYm7xTXKihOBlZTdWH40T/9b/Rw7dIyx0THWrFvD1shW2la33fiHRUREZFFYazl1+BTvvfUe2eEsbaE2tt65lTWb12CM8Tu8qqLkTGSB9CTjJJ7IQksLGXIQ1BplczE+Nk7v3/dy1p6laXsTgWCAgVMDDPztAB/8jg+ycuNKv0MUERFZlvpe6OOdY+/QuK2Ruh11DGWGeGH/C9xx/g627d7md3hVRcmZyM3wesp6IpmJNcrUUzY/J989ydn8WUK7QxNX4dq2tHG59TKvfes1HvvUY7o6JyIiZa8nGSe5a5SQ34EskOz5LIfePURob4iauhoAAo0BGlY08Pb+t+na3kVja6PPUVYPJWci8xRN7yP5o3l3ThkQCmmNspvRf6Sf4C3BaQlYcFWQoXeGyJ7L0rqq1afoREREbqwnGZ+4WFst3wlOHzsNnUwkZkW1DbXY1ZbB9wfZeMdGn6KrPkrORGbLcegJJd27nTlvjbKuqvnw9dv4+DimdnrPmDEGU2sojBd8iEpERGT2nM4coTXVdbF2fHwcaq+xsxa1zwtMyZnIbDgO4d37ybQEIBgEgkQ6Ixq6uIDWbVzHWyffIrgyOGn7WHaMurE6Wla2+BSZiIjILDgORII3fFqlWbVhFfaQxW6zk0a32IKFs9Bxf4eP0VWfJU3OTo6coScZn7StJ9K9lCGIzF4iQU8k497dnZ1Yo0wJ2eLYtGsTR/uOMvzeMK3hVkytYXRolOwbWe659x5qA9e6bCciIiKLpWN9B+tC6zj1+inadrZR21BL/nKei29fZNO6TZpysMCWNDk70wLxPSUbhochGVeCJuXHW6Psak9Zi3rKFllDcwMP/8DDHHz+IKe+eQoC0Bho5L5776NrZ5ff4YmIiCxLxhh2f9duDn37EEf3H6UQKFBbqGXnjp1su2+binUtsCVNztY0r+HJPU9OPE4kE8RrBnDS+4imb64buCcZgljs5gKUZa20Vzf+aXcyr0rhL62m9ibu/577GcuNkR/LE2wOYmr0oS8iImXOcYju6CXZkidUNXUarwrUB7h97+3seGAHo5dHqW+sp7ZOI1oWg69zzmKRGIlkgmRLhmT45l4rvqufTCKhBE3mpbS6kkuJmZ/qgnXUBev8DkNEROTGiolZJ0TCe6t6lE1tXS2NdSqbv5h8LwiyUNVs4r1xQp/uJ5Led9Ov5fTtgWj05oOSstaTjON05gDc9UiqrLqSiIiILJFgkFAoVNWJmSwN35OzhdK9p5tEMkFqzc29TiaTJtyyn5RTslGJWnVwnIm70R29JO9wS+EDhFi4CwUiIiIiIvNRNckZLMyXayflkEz1Et7TSzgXhFwOJ5HScMlK5w05cIt74I4J1xplIiIiIlJGqio5WwjF7uhUJkUKryftiQFSms9WeUp6yoprlIVCIQAiIVVeFBERkQWQSpHak/M7CqkSSs5mMPVLe3E+mwqOVBCvFD4B9088E9QaZSIiIrLAEglCn+53KzxrNI4sgBq/A6gE3Xu6oa2N0Kf7py2iLWXEcdxbyRpl4R17CO/Yo8RMREREFpbjEH08raV3ZEGp52yWuvd0E+/1yq1r4eyy05OMk9idhUCATBQItuiDUkRERBZXMEgoGPI7CqkiSs7moFgRMk6/ErRykEgA0BPJTKxRFumMANOHpoqIiIiIlDslZ3NUXDg7XjOAk96H0/mU3yEtSz3JOIknstDSQoYcoZDWKBMRERGRynbDOWfGmD8yxpwxxhws2dZjjDlhjEl6t+9Z3DDLSywSI7Sqi+SqPNH0vklVAWWReHPJSCSIpvcRvyMLXV2EwxEi4T1KzERkWVIbLSJSXWbTc5YAfhv44ynbf9Na++sLHlGFiEVi7ppo7Ce6o9fNz7RY9eLw1ihL7s1PVF8MhbRGmYgIaqNFRKrKDZMza+1zxpjwEsRScYrzmpKBXsIt+0k5KEFbaI4zsUZZJLxXc8lEREqojRbxSfHCcUueECG/o5EKEu+NX3f/zZTS/zljzBvekIqOm3idihYNR4mE97hl23fvnyhSIQsgkShJzFQKX0RkDtRGiyyWYmK2Kk9olUbyyOzFe+MwPHzd58y3IMjvAv8RsN6/vwH8xExPNMY8CTwJ0L62fZ6HK28TPWipXsJPDJDSYtULIxwGBvyOQkSk0syqjS5tnze1V2f7LLJogkFCq0JKzGRGTsohmU5O2x4azJJ6ZhOG96/5s/PqObPWnrbWjltrC8DvA/df57mft9buttbubmpvms/hKkI0HKU7+hSZVS2EnxhQD9pCiEZJHdhLJA3JI/txUo7fEYmIlL3ZttGl7fPqpuptn0VElpKTckimegkNZunuZdIt9UzXDTtw5tVzZoxZZ6095T38QeDg9Z6/nEQ6I6RySb/DqB7RKI6DO3yA/aQyKV2lEhG5DrXRIiJLq5iQAZDPExkM4PTtnV6LInLj17phcmaM+TMgCqwyxgwAvwpEjTER3CETKeBnZhv8cpAhR08kQ4/fgVSLSQnaAE7K0fwzERHURov4IpUitSfndxTis+KIrlQmRWZwwE3Ivtrp7gyH510kcDbVGj81w+Y/nNfRloFoOEoynSS+axiScXoi3X6HVB28BC28p9fvSEREyobaaJEllkgQfmKATDBAt0byLFuJZIJMJk2IIORyRDIBnM6nIHbzrz3fgiByHd17ukkkE8TpV4K20PJ5UpmU31HMm7WWCycvcKb/DABrNq2hY30HxhifIxMREVneTmezvHbmFNn8KFvbVnL76tXU1dZefYLjEH08TWZVC5HOiEbyLDPFnrJkOgnDw3S/3UZPMuTuXMBCgErOFkksEnMTtJoBnPQ+N5uWmxONEksmidf3E++N072n2++I5mQ8P86rX3uVE4MnMJ1uMtb3jT42rNrAvd95LzW1N7OyhYiIiMzXPx07wp+fOohZZ6htNvzdmcN0pdr4pQ88SEdjo/ukaJRoMkmqJUsq00smkCeZTlbc9xGZu3hvHLJZQvkAoXye2JE2t/MlsvDHUnK2iIoJWpIBoul9OH17tEj1TeqJdEMyTvyOLIlkoqKKgxxLHuP4peN0fLADU+MmZ/ZWy/FXjrMiuYJb773V5whFRESWn/fOn+fPzhxkw32t1NV5PWUb4MTxYRJ9SX7h7gcnntsT6abHcdz7IXcaS7w3TqQzMuk11aNWmWaqDF7sKcs8vclb5olF/T6v5GyRTUrQdvTiOChBu0k9mQhONklqld+RzJ61liNvHaH13taJxAzA1BhatrdwJHlEyZmIiIgPnj31PvUba68mZp71Xa28cfw0gyMjrCpdbsL7HtdDlJ5EgujjaVKZyXPi46leIuE9StIqyEQJ/Cm1XiIZcL66acnWMFZytgRikZj7hrNfCdpCyeXI5DJ+RzFrtmDJ5XKEWkLT9tW11jE0MoQt2EmJm4iIiCy+9JUszc1107YbY6htMgxfuTI5OSsVi+F4PWkTUinCTwyQTPVOzJMPh8JK1MqQk3Im3qNMJk0omyd1YO/0J8aiSxaTkrMlUvwPmQz0Em7ZT8pBCdp8RaM4CfeDL+7sozta/vP5TI2hubWZKxeu0NDRMGnf6IVRWttblZiJiIj4YHNTiKPDF2hvD07aPj5eoHAJVhbnnF3LDN/nUo5DdEcvZDIAJFv2u09VglY2EsmEWwI/2+JuyDHz2mRLTMnZEppI0FK9hHfvJ5VILVkXadWJxUglEoR/OF0Rc8+MMWy/azsH3jhA3X111NS5xT8KYwUuvXOJ++6+z+cIRURElqdHN4T52ptHGVk5RlOT24NmreX40WEebt9EezB4g1eYgbcE0MTDHb0k2T+p4nS5f3cpVexhqqSYZ5JIJibuT6xN1he5+oQy6DhRcrbEouEo0XCUuLOP8BMDpBIJJWjzFQ4TzmVI+R3HLG28fSOXhi9x6LlD4M2XM4OGXbt20bWzy9/gRERElqn1ra382y3383uvvsLZjktQD/Y83N3Qyadvv3P+L1zyRd8hSjS9DwbTACRXjFbExWUomYuVzRPPVMaIpZkkkgkyZ/qJnK8HIJpucQvNdfob11TGWrtkB1u/fb198veeXLLjlbt4b/xq9RclaHPnDRlIdlJRk24vD1/m3MA5jDGs6FpBY+sNhktIWXNSjlvJqQwN/fLQK9ba3X7HIeVv9/r19sCTap9lebs8Nkbf4CC5fJ6utja62toWbR3SnmSc+K5haGub2FZOJfkntW25HJE0OF/tdBfgbgnAfHoT/VZcm6wM1h82n/3sNdtn9Zz5qHtPN/HeOKFP99OtxarnzhsyEKWXZL5yxnI3tjXStUs9ZdWg9Gpi7EiL3+FM81m/AxARqSCNdXXcvW7dkhyruDRQUbEkfzkkaBNzsQYDRNNBIEhPJgKxKKlEgp5IxucI56s8ErMbUXLms2KCJvNUTNBKxnJXwhABqTyJZGJ6hdBc7mplpzIYpz7VZ/9a6ZmISLkqTRR6EglCn+6f8TthpDOy6BefJ7Vx2aw7F6vzqelD/mIxehY1ElFyJpVvUoI2UDFjuKVyTL+KWORdTSzDxExERCpILEZmhl6pxNYsyZy7htpiJWjFaTbdbxeHWLZURA9TtVJyJtWhmKBFKmtxailfs76KKCIishBm6JXqcRzCu/eTTPVOzAFbiJ60ST10ZTQXS5ScSbXJ5W78HJEbmHoVsSfZpaI9IiKy9KJRUg70hJIAOJ05ktmbm8YxvY1TYbpyouRMqkc0SjSZJL6iv2wm1UrliPfGryb3o6OTryJGfApKREQkGqWH6NWH6X0kGSDu7AMgFOq8bqJWLF5VFMrmST1TkpBFFj5kmT8lZ1JVitWP4ruGNfdMbshJOQATFRdTz5RU0dRVRBERKUNO51OQSADQE8kQ39VPIpkgHArP+Hy1cZVFyZnP4s4+Qtm8O2wq4nc01aEn0o2T3kdqjd+RSLmaKIGPW9xjotFSYyUiIpXAa696AJJxEqMDpDKZ6c/L5YhkwOnbC7HoUkUnN0HJmY/ivXF9KVxE08qey00r9jRdT7mtNTdTzFevIoa8LSH9HxQRkYrUE+mmx+tJm1E4rKrCFUTJmc9iR1r0pXARFFexjzv76I4+5Xc4VSHeG4dsllD+2h8bmUCeZDpZNvP9iiXwp8asq4giIlJV9F2yapRNcmat5fyJ8xw/dJwrV66wcu1KNu7YSENzg9+hSSWKxUglEm6CpuIg8+akHFKZlNsLOTxM5ulN7hW4a0mlJpLiUKiTcCi85D1pxZiBibXJnL4905+oq4gis3Y6m+X5k8c5fnmIDY2tfHDdJta1tvodlohI1SmL5Mxay9v73+bdY+8S2BSgdkUtp06e4vCbh/ng936QttVtN34RkaliMWLJOHGtezZnE3OychDOBSGXw/nq7ErtphIJoo+nIZMhFewlnuolEt6zJElasXcvkm2BXI5o2ltIU2uTiczbq+lT/M5738ZugJZV9bxx8TT/8OYRfiZ8Lw+s77rxC4iIyKyVRXJ27vg53k29S/tD7dQEagBo6mzi0olLvPLNV4h+IooxxucopWLlcjgpp+zmQpWbST1OmfTV+ZDFnrLZDgGMxXAcZ+JhcfHM4msvdG9aIpkAmOjd6367jZ5MxN2p3jGRm3JpdJT/duQAK+9poqmpDoAVKxq5vGaMP3jlVXauXE1bg0a4iIgslLJIzvoP9RPYFJhIzIqa1jcx9N4QFwcvqvdM5qUnE8FJ95LM7wfKr1hFuXBSDskj+90eJ4DcTc7JKkmKUg5Ed/SCV0Uq2XJzi2eWmtpTNtvePRGZnYNnznBl5fhEYlbU2FjH6Oosb5xOs3fTLT5FJyJSfcoiOcvlcgRC00MxxmCChrErYz5EJVUhGsVx3OQgycIlBdWg2OMEpXOzIu6GaHThhgJGozhEwetNc9+LgUnHn+17smC9eyIyKyP5MUzQzrivJmjIjql9FhFZSGWRnK1cs5KzZ8/SuLpx0vbCWAGGoaWjxafIpCp4yUE0vW8iKVjuCVoimSBzpp/I+XpvS8Bd1HIx52Z5vWkOUXqScZzONADJFaOzek8m5sFl84Sz7keX81UtQyGymNa3tEK/gc3T99kL0LVeo1pERBZSWSRnm3Zu4siXj3B51WUa17gJWiFfYOiNIW7deqsqNsqCcDqfoicZJ74n43covoj3xq8+KM7NinT7EkvpcXuSceL0T45vJtms17u39+qwydgiBSgiAGxbuZItRzt4//0MXZvaMMZgreXkwEU2Xmln5ypVXBIRWUhlkZw1tjXy0OMP8co3XiFzOINpMDAEW7Zs4fa9t/sdnkjFi/fGJxIyl3+J2VQ9kW5IxmfxzBa30IeKfIgsmRpj+Pm7HuAP33mNN0+dpqbFUMhadtat5qfvuofampobv4iIiMxaWSRnAB3rOnjsU48xdGaIsStjtK5sJdgS9DusRVP8sgwaErLkhoeXxdpnU3vKMk+Xb7GMckkURWS69mCQX7z7QdLZLOcvX6bjliCdLS2qoiwisgjKJjkDMDWGUGfI7zAWXWkvhr6ULq1iL018V/UmaKVzs2JH3PmaPcnyTcxEpDJ0trTQ2aI54CIii6mskrPlRImZfyYStD1+R7JwnJRDMp10H+RybhXDAyVzsyI+BSYiIiIis6bkTKTCTaxRNhjA+apXbjEc1twsERERkQqj5EyWpZ5kiMTWAeLOPrqjT/kdzpwlkgkyGbcUPfm8V8Vwj9b5EhEREalgSs5keYrFSCUShJ8YqJi5Z07KASCVSZE50+8OjU2G3J2x2OKuUSYiIiIii07JmSxfsRixZJx4BSzTE++Nu3PJCEI2S/cRb85ixOfARERERGTBKDkTyeVwUg7RcNTvSCYp9pQl08mr1T2TISCkyosiIiIiVUjJmSxrPZkITrqXZH4/QNkkaHFnH6Gcez+Uz5N6xiuFH/EzKhERERFZTErOlpiTciCbBbRWTFmIRnEciO7oJcl+UpkUsUhsycNwUg6pTAqATCbtlsJ/psutuggq9CEiIiKyDCg5W0KJZILM4ACRwQA9mYjf4UhRNIpDlGh6H0kGSCQTS5qgTSwanYNwLgg5cPr2KiETERERWWZumJwZY/4I+D7gjLX2Dm/bCuAvgDCQAj5prb2weGFWh0wuc7XkeZWuQXU6m+XFY8cYOHOGhvp67gqHuXfDBgI1NX6HdkNO51P0JOPEI+lFn4OWSCYm7hcTdqevZFXsKv37EJGFpTZaZuvS6Ci9/f28OzCAtZbburp4YNMmWhsa/A5NRErM5htzAnh8yrangK9ba7cBX/ceyyxE08Gq/eJ99MIFvvDNb7Lq6FE+OT7OY9kshw8c4Isvv0y+UPA7vFnpSYbcioiLqNiDGk5lCKemJOzFm4jI7CRQGy03MHzlCr//rW9x+eBBfuDKFT42OsrYW2/x+889RyaX8zs8ESlxw54za+1zxpjwlM0fBaLe/S8ADvDvFzIwqSzWWv7u1Vf5eCDArY2NAKwBNgeD/MnJk7yeTnPv+vX+Bjlb2SzJdHJBe84m9ZQV1ygrDm2NRrVGmYjMi9pomQ3nyBHuvHiRx0KhiW3rGxpoGhri64cO8fEPfMC/4ERkkvmONVtrrT0F4P27ZuFCkkp0KpulNptlS3Byr5MxhvsbGnirv9+nyOYoFiN2pAWGh921xRZAvDdO5kw/4b404b60m5hFutVLJiKLRW20TLDWcvDYMR5obZ227/6WFt55/30K1voQmYjMZNELghhjngSeBGhf277YhxOfjI6P04ibjE3VVFPD6NjY0gc1Tz2RbnoSCUKx+c89m5TYFdcoi3S7j9VLJiJloLR93tSu9rmajeXzNM4w97uhpgZbKFCwlpoZ2m8RWXrz7Tk7bYxZB+D9e+ZaT7TWft5au9tau7upvWmeh5Nyt66lhTO1tVzM56fteyeX45bOystI5jv3LO7sIzSYpbsXunsh8/Smq4mZiMjim1UbXdo+r25S+1ytjDFsWruWvpGRafsOX75M56pVFVG0S2S5mG/P2d8AnwH2ef/+9YJFJBWpIRDg/h07+NIbb/DxtjZCgQAFa3nj0iXeaGjgyY0b/Q5x7rJZkqle4PqLUzsph2Q66T7I5a6uURaLudsiixmkiMg0aqNlkke2b+evnnuOllyOTQ0NGGM4nsvx96OjfO+OHX6HJyIlZlNK/89wJxavMsYMAL+K+4H/JWPMTwL9wCcWM0ipDB+69VZqa2r4fF8frZcucQkIrVrFj33gA7QHF7cC4oKLxUglEoSfGLhugjaxRlk2785VI+gW+tAaZSKyBNRGy2zcumIF3/PQQ/z1m2/C8DAGGG9q4jsffJDtq1b5HZ6IlJhNtcZPXWPXYwscS1WLO/sIZfP0JLuqtifFGMOjW7bw0C23MDgyQjAQoMOr3FiRiglaLDNpcyKZIJNJuw/yea8U/l4V9xCRJac2WmZr55o17Pjwhzk7MoK1ltXNzZpnJlKGFr0giLjFIaYNdatidbW1rJuhKlQ1KK5RFhkM4HzVm0cXDisxExGRsmeMYU1zs99hiMh1KDlbCrncsknMqk44TDjdSzK/3x3eODp6tfJizO/gRERERKSaKDlbZE7K8TsEuRnRKI4DpFJXtynJFhEREZFFoORsERWLRUTSuEPfpDJpyKKIiIiILAElZ4tk0tykvj36gi8iIiIiItelVQcXgRIzERERERGZK/WcLbBJiVnnU9Dpd0QiIiIiIlIJ1HO2gBLJBJkz/XQfbHETMxERERERkVlScrZAnJRDJpO+WmZdRERERERkDpScLaAQQXqSIb/DEBERERGRCqQ5ZwskmU4SymaBkN+hiMwonc3y3OHDHDlxAmMMOzZu5NFt21jR2Oh3aBWlYC0vDwzw8uHDXMhm6Whp4f7bbuO+DRswxvgdnoiIVJhLo6M8d/Qobx47xujYGJvWruXh225jc0eH36FVnMPnzrH/3Xc5cfYswfp67tqyhUe2bCEYqJyUp3IiLWPx3jihwSypZ7q0QLGUpRPDw3zxW9/i0fFxvr+5mXHg1WPH+KNTp/iJRx5RgjYHf/vWW5x/910+2tTEutZWTl65wte+/W1Ob9/O999+u9/hiYhIBbk8NsYfvfACt164wE+3tNDc0EDf2bN8OZ3mex98kJ1r1vgdYsVInjrFN196ie+qq2NrSwsXx8fZ/9ZbJE6f5iceeoj62lq/Q5wVDWu8CU7KIe7sU2ImZe/r77zDdxQKPNDWRmNtLS21tTzS3s59uRzPHTnid3gV49TFi7x35Ag/GgqxMRgkYAybgkF+LBTi3cOHOXPpkt8hiohIBXl5YICuCxf4no4OOurqqK+p4a6WFj7R0MA/v/EGBWv9DrEi5AsFvvb663y6qYldzc3U19Swsq6OHwiFaB8cJHnqlN8hzpqSs3lyUg7JVC+hbF6JmZS10fFxjqfT3NnSMm3fPc3N9B0/7kNUlenQ4CB3WUtdzeSPzvqaGu6wlr6zZ32KTEREKlHf8ePcM8PolU0NDdRcuqSLfrM0MDxMx5UrrK2vn7TdGMM9DQ30DQz4FNncaVjjPExKzA7shVjU75BErslaC9bOeCWm1hgKhcKSx1SpCtZSc415ZbXefhERkdmy1lI7Q7tijKHWWrUrs1S4xvccqLzvOuo5myMn5ZA8sp9IGjcxi0b9DknkuhoCATpXr6ZvZGTavjcuXWLbhg0+RFWZtq5cyVvA+JTGctxa3jKGbStX+hOYiIhUpK0bNvDG5cvTtqdHR7nc2Mja5mYfoqo8XW1tnA0EuDA2Nm3fG7lcRX3XUXI2B4lkwk3MBgM4fXuUmEnF+NCuXfx9Ps/bly5RsJa8tbx68SLP1dby8LZtfodXMTa2tbFq40aeyWQmGoDzY2N86cIFOm+5hQ1tbT5HKCIileT+jRvpa27mW0NDXCkUsNZy7PJl/uLSJT50553U1uir+mzU19byyJ138vTFixzP5bDWcnl8nG8MDXG8vZ171q/3O8RZ07DGWUokE2QGB9zErPMp6PQ7IpHZ29LRwccfeYRvvv02Xzl7Foxh07p1/OjOnXTOMBdNZmaM4RN3343T1sbvHzlC4dIlahoauPeuu3h0yxa/wxMRkQrT2tDAj+/dy9f6+vj148epKRRoD4V47J57uGPtWr/DqygPbtpEMBDgr/r6yA4NYWtr2bF5Mz++fTuNdXV+hzdrSs7mIJJtwemLKDGTirSlo4MtH/wgV/J5jDEVU1K23ARqavjItm18eOtWcvk8wUDgmvPQREREbqSjsZFP3n03Y3fdRb5QIBgIaN3Mebp7/Xoi69aRy+epq60lUIE9j0rO5iKX8zsCkZvWUEELMZazGmNoqqArcSIiUt7qamup04XTm2aMqaiesqn0LW0W4r1xGB4mmm7TPDMREREREVkUldfXt8SKiVn32230RLr9DkdERERERKqUes6uo5iYZZ7epEWmRURERERkUSk5u4a4s89dZPoZJWYiIiIiIrL4lJxN4aQckqleLzHrUmImIiIiIiJLQsnZFKlMyk3MDuyFWNTvcEREREREZJlQQZAZhLMBVWUUEREREZElpeSshJNyyAwO+B2GiIiIiIgsQxrW6EkkE2QGB4gMBnD69kCn3xGJiIiIiMhyouSMKYlZ51NKzEREREREZMkt+2GNiWSCzJl+ug+2uImZiIiIiIiID5Z1z1lxkenut9voiXT7HY6IiIiIiCxjy7bnTImZiIiIiIiUk2XZc1ZMzDJPb9Ii0yIiIiIiUhaWXc9ZvDdOaDCrxExERERERMrKskvOAGJHWpSYiYiIiIhIWVlWyZmTciCX8zsMERERERGRaZZNcuakHJKpXkLZPD2ZiN/hiIiIiIiITLIsCoI4KYfkkf3uItN9eyEa9TuksmCt5cj587x98iT58XHCa9Zw19q11NXW+h2aiIjIsnY6m+W1Eye4ODLCmlCIe9avp7Whwe+wRGSR3VRyZoxJAReBcSBvrd29EEEtpEQyQWZwwEvM9igx8xSs5ZlkknPvv889NTU01NTwdirFC6EQsQcfVAMgIlLhKqGNlpm92N/P86+9xm5gQ20t/f39/O477/DJhx4iHAr5HZ6ILKKF6Dn7kLV2cAFeZ8EpMbu2V06cYOTYMZ7s6KDWGAAiwDeGhviHt97iX91zj6/xiYjIgijbNlpmdubSJZ5/7TWebG6mLeB+TbsT2Hn5Ms+89BK/8B3fQW3NspmVIrLsVO3/7mJi1n2wBafzKSVmU7x29CiPNDZOJGZFH2xt5djAACNjYz5FJiIisnwlT5zgHphIzIq2NDay8vJlDp8/709gIrIkbjY5s8A/G2NeMcY8OdMTjDFPGmMOGGMOjAyN3OThZsdJOWQyaboPttAT6V6SY1aa7OXLrKyrm7a9oaaGJmu5rORMRKTSXbeNLm2fz44sTfssN5a9fJmV15j7vRK4NDq6tAGJyJK62eTsg9bae4DvBn7WGPPI1CdYaz9vrd1trd3d1N50k4ebvRBBepKhJTtepVnT0UFqhmUFMvk8lwMB2jTnTESk0l23jS5tn1c3LV37LNe3pr2dVD4/bbu1lveBNc3NSx+UiCyZm0rOrLUnvX/PAF8B7l+IoG5WMp2EbNbvMMrag1u38o2xMc6X9JCNFgr83cWL3HvbbarYKCJS4cq1jZbru3v9et5taODdkt5May3O8DCNa9bQ1dbmY3QistjmXRDEGNMM1FhrL3r3vxP4DwsW2TzFe+MwPEzqmU0Qi/kdTtm6dcUKHr7vPj6fTLLp0iUagPeMYcdtt/GhW2/1OzwREbkJ5dpGy40119fzww89xDMvv8y3MhlWGkO/tTSvWcO/uvdezJS54iJSXW6mWuNa4Cveh0QAeNpa+9UFiWqe4s4+Qtm8ErNZ2t3VxZ2dnRw+f558ocBjoRChYNDvsERE5OaVXRsts7exvZ2ff+wx3jt/nuzoKPc1N7O+tVWJmcgyMO/kzFp7FPjAAsYyb07KIZnq9RKzLiVmc9AQCHDHmjV+hyEiIguonNpomZ8aY9i2cqXfYYjIEqv4UvpKzEREREREpBosxCLUvpmUmB3YC7Go3yGJiIiIiIjMS8X2nDkph+SR/UTSuImZFpkWEREREZEKVpHJWbHHLDIYwOnbo8RMREREREQqnrHWLt3BjDkLvD+Lp64CBhc5nKVUTedTTecCOp9yVk3nAv6czy3W2tVLfEypQHNon6G6/m9W07lAdZ1PNZ0LVNf5VNO5QJm1z0uanM2WMeaAtXa333EslGo6n2o6F9D5lLNqOheovvOR5aua/par6Vygus6nms4Fqut8qulcoPzOpyKHNYqIiIiIiFQbJWciIiIiIiJloFyTs8/7HcACq6bzqaZzAZ1POaumc4HqOx9Zvqrpb7mazgWq63yq6Vygus6nms4Fyux8ynLOmYiIiIiIyHJTrj1nIiIiIiIiy0rZJWfGmJQx5k1jTNIYc8DveObKGPNHxpgzxpiDJdtWGGO+Zow57P3b4WeMs3WNc+kxxpzw3p+kMeZ7/IxxtowxG40x3zTGvGOMecsY8/Pe9kp9b651PpX6/gSNMd82xrzunc9nve0V9/5c51wq8r0RKVL7XD6qqX2G6mqj1T6Xr0ppn8tuWKMxJgXsttZW5PoJxphHgCzwx9baO7xt/xU4b63dZ4x5Cuiw1v57P+OcjWucSw+Qtdb+up+xzZUxZh2wzlr7qjGmFXgF+BgQozLfm2udzyepzPfHAM3W2qwxpg7YD/w88ENU2PtznXN5nAp8b0SK1D6Xj2pqn6G62mi1z+WrUtrnsus5q3TW2ueA81M2fxT4gnf/C7j/ScveNc6lIllrT1lrX/XuXwTeATZQue/Ntc6nIllX1ntY590sFfj+XOdcRMRHap/LVzW10Wqfy1eltM/lmJxZ4J+NMa8YY570O5gFstZaewrc/7TAGp/juVk/Z4x5wxtWUfbd2FMZY8LA3cBLVMF7M+V8oELfH2NMrTEmCZwBvmatrdj35xrnAhX63oh41D6Xv4r/jKmmNlrtc/mphPa5HJOzD1pr7wG+G/hZr+teysfvArcCEeAU8Bu+RjNHxpgW4MtAt7V22O94btYM51Ox74+1dtxaGwG6gPuNMXf4HNK8XeNcKva9EfGofS5vFf8ZU01ttNrn8lQJ7XPZJWfW2pPev2eArwD3+xvRgjjtjUEujkU+43M882atPe39YReA36eC3h9vfPGXgS9aa//S21yx781M51PJ70+RtTYDOLhjwCv2/YHJ51IN740sb2qfy1ulf8ZUUxut9rn8lXP7XFbJmTGm2Zs8iTGmGfhO4OD1f6oi/A3wGe/+Z4C/9jGWm1L8j+j5QSrk/fEmgf4h8I619nMluyryvbnW+VTw+7PaGBPy7jcCHwH6qMD351rnUqnvjQiofa4ElfwZU01ttNrn8lUp7XNZVWs0xmzBvRoHEACettb+nz6GNGfGmD8DosAq4DTwq8BfAV8CNgH9wCestWU/kfca5xLF7fa1QAr4meKY43JmjNkLfAt4Eyh4m38Fdxx4Jb431zqfT1GZ789duBOKa3EvGn3JWvsfjDErqbD35zrn8idU4HsjAmqfy001tc9QXW202ufyVSntc1klZyIiIiIiIstVWQ1rFBERERERWa6UnImIiIiIiJQBJWciIiIiIiJlQMmZiIiIiIhIGVByJiIiIiIiUgaUnImIiIiIiJQBJWciIiIiIiJlQMmZiIiIiIhIGfj/AWy/Hn7YZl+gAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 1080x360 with 2 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "# 设置图形标题\n",
    "titles = ('K Neighbors with k=1',\n",
    "          'K Neighbors with k=2')\n",
    "\n",
    "# 设置图形的大小和图间距\n",
    "fig = plt.figure(figsize=(15, 5))\n",
    "plt.subplots_adjust(wspace=0.4, hspace=0.4)\n",
    "\n",
    "# 分别获取第1个和第2个特征向量\n",
    "X0, X1 = X_train[:, 0], X_train[:, 1]\n",
    "\n",
    "# 得到坐标轴的最小值和最大值\n",
    "x_min, x_max = X0.min() - 1, X0.max() + 1\n",
    "y_min, y_max = X1.min() - 1, X1.max() + 1\n",
    "\n",
    "# 构造网格点坐标矩阵\n",
    "# 设置0.2的目的是生成更多的网格点，数值越小，划分空间之间的分隔线越清晰\n",
    "xx, yy = np.meshgrid(np.arange(x_min, x_max, 0.2),\n",
    "                     np.arange(y_min, y_max, 0.2))\n",
    "\n",
    "for clf, title, ax in zip(models, titles, fig.subplots(1, 2).flatten()):\n",
    "    # （2）使用matplotlib的contourf和scatter，画出k为1和2时的k近邻法构成的空间划分\n",
    "    # 对所有网格点进行预测\n",
    "    Z = clf.predict(np.c_[xx.ravel(), yy.ravel()])\n",
    "    Z = Z.reshape(xx.shape)\n",
    "    # 设置颜色列表\n",
    "    colors = ('red', 'green', 'lightgreen', 'gray', 'cyan')\n",
    "    # 根据类别数生成颜色\n",
    "    cmap = ListedColormap(colors[:len(np.unique(Z))])\n",
    "    # 绘制分隔线，contourf函数用于绘制等高线，alpha表示颜色的透明度，一般设置成0.5\n",
    "    ax.contourf(xx, yy, Z, cmap=cmap, alpha=0.5)\n",
    "\n",
    "    # 绘制样本点\n",
    "    ax.scatter(X0, X1, c=y_train, s=50, edgecolors='k', cmap=cmap, alpha=0.5)\n",
    "\n",
    "    # （3）根据模型得到的预测结果，计算预测准确率，并设置图形标题\n",
    "    # 计算预测准确率\n",
    "    acc = clf.score(X_train, y_train)\n",
    "    # 设置标题\n",
    "    ax.set_title(title + ' (Accuracy: %d%%)' % (acc * 100))\n",
    "\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> **补充知识：**   \n",
    "np.meshgrid方法：用于构造网格点坐标矩阵，可参考https://blog.csdn.net/lllxxq141592654/article/details/81532855"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**第4步：比较$k$为1和2时，k值选择与模型复杂度、预测准确率的关系**\n",
    "\n",
    "1. $k$值选择与模型复杂度的关系  \n",
    "&emsp;&emsp;根据书中第52页（3.2.3节：$k$值的选择）\n",
    "  > &emsp;&emsp;如果选择较小的$k$值，就相当于用较小的邻域中的训练实例进行预测，“学习”的近似误差会减小，只有与输入实例较近的（相似的）训练实例才会对预测结果起作用。$k$值的减小就意味着整体模型变得复杂，容易发生过拟合。  \n",
    "  > &emsp;&emsp;如果选择较大的$k$值，就相当于用较大邻域中的训练实例进行预测。$k$值的增大就意味着整体的模型变得简单。\n",
    "\n",
    "  &emsp;&emsp;综上所属，$k$值越大，模型复杂度越低，模型越简单，容易发生欠拟合。反之，$k$值越小，模型越复杂，容易发生过拟合。\n",
    "  \n",
    "  \n",
    "2. $k$值选择与预测准确率的关系  \n",
    "&emsp;&emsp;从图中观察到，当$k=1$时，模型易产生过拟合，当$k=2$时准确率仅有88%，故在过拟合发生前，$k$值越大，预测准确率越低，也反映模型泛化能力越差，模型简单。反之，$k$值越小，预测准确率越高，模型具有更好的泛化能力，模型复杂。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 习题3.2\n",
    "&emsp;&emsp;利用例题3.2构造的$kd$树求点$x=(3,4.5)^T$的最近邻点。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**解答：**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**解答思路：**  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**方法一：**\n",
    "1. 使用sklearn的KDTree类，结合例题3.2构建平衡$kd$树，配置相关参数（构建平衡树kd树算法，见书中第54页算法3.2内容）；\n",
    "2. 使用tree.query方法，查找(3, 4.5)的最近邻点（搜索kd树算法，见书中第55页第3.3.2节内容）；\n",
    "3. 根据第3步返回的参数，得到最近邻点。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**方法二：**  \n",
    "&emsp;&emsp;根据书中第56页算法3.3用$kd$树的最近邻搜索方法，查找(3, 4.5)的最近邻点"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**解答步骤：**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**方法一：**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "x点(3,4.5)的最近邻点是(2, 3)\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "from sklearn.neighbors import KDTree\n",
    "\n",
    "# 构造例题3.2的数据集\n",
    "train_data = np.array([[2, 3],\n",
    "                       [5, 4],\n",
    "                       [9, 6],\n",
    "                       [4, 7],\n",
    "                       [8, 1],\n",
    "                       [7, 2]])\n",
    "# （1）使用sklearn的KDTree类，构建平衡kd树\n",
    "# 设置leaf_size为2，表示平衡树\n",
    "tree = KDTree(train_data, leaf_size=2)\n",
    "\n",
    "# （2）使用tree.query方法，设置k=1，查找(3, 4.5)的最近邻点\n",
    "# dist表示与最近邻点的距离，ind表示最近邻点在train_data的位置\n",
    "dist, ind = tree.query(np.array([[3, 4.5]]), k=1)\n",
    "node_index = ind[0]\n",
    "\n",
    "# （3）得到最近邻点\n",
    "x1 = train_data[node_index][0][0]\n",
    "x2 = train_data[node_index][0][1]\n",
    "print(\"x点(3,4.5)的最近邻点是({0}, {1})\".format(x1, x2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "可得到点$x=(3,4.5)^T$的最近邻点是$(2,3)^T$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**方法二：** "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. 首先找到点$x=(3,4.5)^T$所在领域的叶节点$x_1=(4,7)^T$，则最近邻点一定在以$x$为圆心，$x$到$x_1$距离为半径的圆内；\n",
    "2. 找到$x_1$的父节点$x_2=(5,4)^T$，$x_2$的另一子节点为$x_3=(2,3)^T$，此时$x_3$在圆内，故$x_3$为最新的最近邻点，并形成以$x$为圆心，以$x$到$x_3$距离为半径的圆；\n",
    "3. 继续探索$x_2$的父节点$x_4=(7,2)^T$,$x_4$的另一个子节点$(9,6)$对应的区域不与圆相交，故不存在最近邻点，所以最近邻点为$x_3=(2,3)^T$。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "可得到点$x=(3,4.5)^T$的最近邻点是$(2,3)^T$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 习题3.3\n",
    "&emsp;&emsp;参照算法3.3，写出输出为$x$的$k$近邻的算法。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**解答：**\n",
    "\n",
    "**解答思路：**\n",
    "1. 参考书中第56页算法3.3（用$kd$树的最近邻搜索），写出输出为$x$的$k$近邻算法；\n",
    "2. 根据算法步骤，写出算法代码，并用习题3.2的解进行验证。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**解答步骤：**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**第1步：用$kd$树的$k$邻近搜索算法**\n",
    "\n",
    "根据书中第56页算法3.3（用$kd$树的最近邻搜索）\n",
    "> 输入：已构造的kd树；目标点$x$；    \n",
    "输出：$x$的k近邻    \n",
    "（1）在$kd$树中找出包含目标点$x$的叶结点：从根结点出发，递归地向下访问树。若目标点$x$当前维的坐标小于切分点的坐标，则移动到左子结点，否则移动到右子结点，直到子结点为叶结点为止；  \n",
    "（2）如果“当前$k$近邻点集”元素数量小于$k$或者叶节点距离小于“当前$k$近邻点集”中最远点距离，那么将叶节点插入“当前k近邻点集”；  \n",
    "（3）递归地向上回退，在每个结点进行以下操作：  \n",
    "&emsp;&emsp;（a）如果“当前$k$近邻点集”元素数量小于$k$或者当前节点距离小于“当前$k$近邻点集”中最远点距离，那么将该节点插入“当前$k$近邻点集”。  \n",
    "&emsp;&emsp;（b）检查另一子结点对应的区域是否与以目标点为球心、以目标点与“当前$k$近邻点集”中最远点间的距离为半径的超球体相交。  \n",
    "&emsp;&emsp;如果相交，可能在另一个子结点对应的区域内存在距目标点更近的点，移动到另一个子结点，接着，递归地进行近邻搜索；  \n",
    "&emsp;&emsp;如果不相交，向上回退；  \n",
    "（4）当回退到根结点时，搜索结束，最后的“当前$k$近邻点集”即为$x$的近邻点。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**第2步：根据算法步骤，写出算法代码，并用习题3.2的解进行验证**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "import json\n",
    "\n",
    "\n",
    "class Node:\n",
    "    \"\"\"节点类\"\"\"\n",
    "\n",
    "    def __init__(self, value, index, left_child, right_child):\n",
    "        self.value = value.tolist()\n",
    "        self.index = index\n",
    "        self.left_child = left_child\n",
    "        self.right_child = right_child\n",
    "\n",
    "    def __repr__(self):\n",
    "        return json.dumps(self, indent=3, default=lambda obj: obj.__dict__, ensure_ascii=False, allow_nan=False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "class KDTree:\n",
    "    \"\"\"kd tree类\"\"\"\n",
    "\n",
    "    def __init__(self, data):\n",
    "        # 数据集\n",
    "        self.data = np.asarray(data)\n",
    "        # kd树\n",
    "        self.kd_tree = None\n",
    "        # 创建平衡kd树\n",
    "        self._create_kd_tree(data)\n",
    "\n",
    "    def _split_sub_tree(self, data, depth=0):\n",
    "        # 算法3.2第3步：直到子区域没有实例存在时停止\n",
    "        if len(data) == 0:\n",
    "            return None\n",
    "        # 算法3.2第2步：选择切分坐标轴, 从0开始（书中是从1开始）\n",
    "        l = depth % data.shape[1]\n",
    "        # 对数据进行排序\n",
    "        data = data[data[:, l].argsort()]\n",
    "        # 算法3.2第1步：将所有实例坐标的中位数作为切分点\n",
    "        median_index = data.shape[0] // 2\n",
    "        # 获取结点在数据集中的位置\n",
    "        node_index = [i for i, v in enumerate(\n",
    "            self.data) if list(v) == list(data[median_index])]\n",
    "        return Node(\n",
    "            # 本结点\n",
    "            value=data[median_index],\n",
    "            # 本结点在数据集中的位置\n",
    "            index=node_index[0],\n",
    "            # 左子结点\n",
    "            left_child=self._split_sub_tree(data[:median_index], depth + 1),\n",
    "            # 右子结点\n",
    "            right_child=self._split_sub_tree(\n",
    "                data[median_index + 1:], depth + 1)\n",
    "        )\n",
    "\n",
    "    def _create_kd_tree(self, X):\n",
    "        self.kd_tree = self._split_sub_tree(X)\n",
    "\n",
    "    def query(self, data, k=1):\n",
    "        data = np.asarray(data)\n",
    "        hits = self._search(data, self.kd_tree, k=k, k_neighbor_sets=list())\n",
    "        dd = np.array([hit[0] for hit in hits])\n",
    "        ii = np.array([hit[1] for hit in hits])\n",
    "        return dd, ii\n",
    "\n",
    "    def __repr__(self):\n",
    "        return str(self.kd_tree)\n",
    "\n",
    "    @staticmethod\n",
    "    def _cal_node_distance(node1, node2):\n",
    "        \"\"\"计算两个结点之间的距离\"\"\"\n",
    "        return np.sqrt(np.sum(np.square(node1 - node2)))\n",
    "\n",
    "    def _search(self, point, tree=None, k=1, k_neighbor_sets=None, depth=0):\n",
    "         n = point.shape[1]\n",
    "        if k_neighbor_sets is None:\n",
    "            k_neighbor_sets = []\n",
    "        if tree is None:\n",
    "            return k_neighbor_sets\n",
    "\n",
    "        # (1)找到包含目标点x的叶结点\n",
    "        if tree.left_child is None and tree.right_child is None:\n",
    "            # 更新当前k近邻点集\n",
    "            return self._update_k_neighbor_sets(k_neighbor_sets, k, tree, point)\n",
    "\n",
    "        # 递归地向下访问kd树\n",
    "        if point[0][depth % n] < tree.value[depth % n]:\n",
    "            direct = 'left'\n",
    "            next_branch = tree.left_child\n",
    "        else:\n",
    "            direct = 'right'\n",
    "            next_branch = tree.right_child\n",
    "        if next_branch is not None:\n",
    "            # (3)(b)检查另一子结点对应的区域是否相交\n",
    "            k_neighbor_sets = self._search(point, tree=next_branch, k=k, depth=depth + 1,\n",
    "                                           k_neighbor_sets=k_neighbor_sets)\n",
    "\n",
    "            # 计算目标点与切分点形成的分割超平面的距离\n",
    "            temp_dist = abs(tree.value[depth % n] - point[0][depth % n])\n",
    "\n",
    "            if direct == 'left':\n",
    "                # 判断超球体是否与超平面相交\n",
    "                if not (k_neighbor_sets[0][0] < temp_dist and len(k_neighbor_sets) == k):\n",
    "                    # 如果相交，递归地进行近邻搜索\n",
    "                    # (3)(a) 判断当前结点，并更新当前k近邻点集\n",
    "                    k_neighbor_sets = self._update_k_neighbor_sets(k_neighbor_sets, k, tree, point)\n",
    "                    return self._search(point, tree=tree.right_child, k=k, depth=depth + 1,\n",
    "                                        k_neighbor_sets=k_neighbor_sets)\n",
    "            else:\n",
    "                # 判断超球体是否与超平面相交\n",
    "                if not (k_neighbor_sets[0][0] < temp_dist and len(k_neighbor_sets) == k):\n",
    "                    # 如果相交，递归地进行近邻搜索\n",
    "                    # (3)(a) 判断当前结点，并更新当前k近邻点集\n",
    "                    k_neighbor_sets = self._update_k_neighbor_sets(k_neighbor_sets, k, tree, point)\n",
    "                    return self._search(point, tree=tree.left_child, k=k, depth=depth + 1,\n",
    "                                        k_neighbor_sets=k_neighbor_sets)\n",
    "        else:\n",
    "            return self._update_k_neighbor_sets(k_neighbor_sets, k, tree, point)\n",
    "\n",
    "        return k_neighbor_sets\n",
    "\n",
    "    def _update_k_neighbor_sets(self, best, k, tree, point):\n",
    "        # 计算目标点与当前结点的距离\n",
    "        node_distance = self._cal_node_distance(point, tree.value)\n",
    "        if len(best) == 0:\n",
    "            best.append((node_distance, tree.index, tree.value))\n",
    "        elif len(best) < k:\n",
    "            # 如果“当前k近邻点集”元素数量小于k\n",
    "            self._insert_k_neighbor_sets(best, tree, node_distance)\n",
    "        else:\n",
    "            # 叶节点距离小于“当前 𝑘 近邻点集”中最远点距离\n",
    "            if best[0][0] > node_distance:\n",
    "                best = best[1:]\n",
    "                self._insert_k_neighbor_sets(best, tree, node_distance)\n",
    "        return best\n",
    "\n",
    "    @staticmethod\n",
    "    def _insert_k_neighbor_sets(best, tree, node_distance):\n",
    "        \"\"\"将距离最远的结点排在前面\"\"\"\n",
    "        n = len(best)\n",
    "        for i, item in enumerate(best):\n",
    "            if item[0] < node_distance:\n",
    "                # 将距离最远的结点插入到前面\n",
    "                best.insert(i, (node_distance, tree.index, tree.value))\n",
    "                break\n",
    "        if len(best) == n:\n",
    "            best.append((node_distance, tree.index, tree.value))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 打印信息\n",
    "def print_k_neighbor_sets(k, ii, dd):\n",
    "    if k == 1:\n",
    "        text = \"x点的最近邻点是\"\n",
    "    else:\n",
    "        text = \"x点的%d个近邻点是\" % k\n",
    "\n",
    "    for i, index in enumerate(ii):\n",
    "        res = X_train[index]\n",
    "        if i == 0:\n",
    "            text += str(tuple(res))\n",
    "        else:\n",
    "            text += \", \" + str(tuple(res))\n",
    "\n",
    "    if k == 1:\n",
    "        text += \"，距离是\"\n",
    "    else:\n",
    "        text += \"，距离分别是\"\n",
    "    for i, dist in enumerate(dd):\n",
    "        if i == 0:\n",
    "            text += \"%.4f\" % dist\n",
    "        else:\n",
    "            text += \", %.4f\" % dist\n",
    "\n",
    "    print(text)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "x点的最近邻点是(2, 3)，距离是1.8028\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "\n",
    "X_train = np.array([[2, 3],\n",
    "                    [5, 4],\n",
    "                    [9, 6],\n",
    "                    [4, 7],\n",
    "                    [8, 1],\n",
    "                    [7, 2]])\n",
    "kd_tree = KDTree(X_train)\n",
    "# 设置k值\n",
    "k = 1\n",
    "# 查找邻近的结点\n",
    "dists, indices = kd_tree.query(np.array([[3, 4.5]]), k=k)\n",
    "# 打印邻近结点\n",
    "print_k_neighbor_sets(k, indices, dists)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{\n",
       "   \"value\": [\n",
       "      7,\n",
       "      2\n",
       "   ],\n",
       "   \"index\": 5,\n",
       "   \"left_child\": {\n",
       "      \"value\": [\n",
       "         5,\n",
       "         4\n",
       "      ],\n",
       "      \"index\": 1,\n",
       "      \"left_child\": {\n",
       "         \"value\": [\n",
       "            2,\n",
       "            3\n",
       "         ],\n",
       "         \"index\": 0,\n",
       "         \"left_child\": null,\n",
       "         \"right_child\": null\n",
       "      },\n",
       "      \"right_child\": {\n",
       "         \"value\": [\n",
       "            4,\n",
       "            7\n",
       "         ],\n",
       "         \"index\": 3,\n",
       "         \"left_child\": null,\n",
       "         \"right_child\": null\n",
       "      }\n",
       "   },\n",
       "   \"right_child\": {\n",
       "      \"value\": [\n",
       "         9,\n",
       "         6\n",
       "      ],\n",
       "      \"index\": 2,\n",
       "      \"left_child\": {\n",
       "         \"value\": [\n",
       "            8,\n",
       "            1\n",
       "         ],\n",
       "         \"index\": 4,\n",
       "         \"left_child\": null,\n",
       "         \"right_child\": null\n",
       "      },\n",
       "      \"right_child\": null\n",
       "   }\n",
       "}"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 打印kd树\n",
    "kd_tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "&emsp;&emsp;上述打印的平衡kd树和书中第55页的图3.4 kd树示例一致。\n",
    "\n",
    "![3-1-KD-Tree-Demo.png](./images/3-1-KD-Tree-Demo.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "更换数据集，使用更高维度的数据，并设置$k=3$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "x点的3个近邻点是(4, 7, 4), (5, 4, 4), (2, 3, 4)，距离分别是2.6926, 2.0616, 1.8028\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "\n",
    "X_train = np.array([[2, 3, 4],\n",
    "                    [5, 4, 4],\n",
    "                    [9, 6, 4],\n",
    "                    [4, 7, 4],\n",
    "                    [8, 1, 4],\n",
    "                    [7, 2, 4]])\n",
    "kd_tree = KDTree(X_train)\n",
    "# 设置k值\n",
    "k = 3\n",
    "# 查找邻近的结点\n",
    "dists, indices = kd_tree.query(np.array([[3, 4.5, 4]]), k=k)\n",
    "# 打印邻近结点\n",
    "print_k_neighbor_sets(k, indices, dists)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.9"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
